class Solution {
public:
    int magicalString(int n) {
        if(n <= 3)
        {
            return 1;
        }
        string s = "122";
        s.reserve(n);
        int nextVal = 1;
        int nextCountPtr = 2;
        int oneCount = 1;
        while(s.size() <= n - 2)
        {
            int nextCount = s[nextCountPtr] - '0';
            for(int i = 0; i < nextCount; ++i)
            {
                s.push_back(static_cast<char>(nextVal + '0'));
            }
            if(nextVal == 1)
            {
                oneCount += nextCount;
            }
            nextVal = 3 - nextVal;
            ++nextCountPtr;

        }
        // 此时s的size为n-1或n
        if(s.size() == n - 1 && nextVal == 1)
        {
            ++oneCount;
        }
        return oneCount;
    }
};